package com.test.daily.leetcode.y2022.m06.day0608.v04;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/8 下午 09:42
 * @version: 1.0
 */
public class Solution {
    public static int minSnacks(String[] snacks, String target){
        if(snacks == null || target == null || snacks.length == 0){
            return 0;
        }
        int min = process(snacks, target);
        return min == Integer.MAX_VALUE ? -1 : min;
    }
    public static int process(String[] snacks, String target){
        int min = Integer.MAX_VALUE;
        for(String first: snacks){
            String rest = minus(target, first);
            if(rest.length() != target.length()){
                min = Math.min(min, process(snacks, rest));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0: min+1);
    }
    public static String minus(String target, String cur){
        char[] strTarget = target.toCharArray();
        char[] strCur = cur.toCharArray();
        int[] count = new int[26];
        for(Character ch : strTarget){
            count[ch - 'a'] ++;
        }
        for(Character ch: strCur){
            count[ch - 'a']--;
        }
        StringBuilder builder = new StringBuilder();
        for(int i = 0; i < 26; i++){
            if(count[i] > 0){
                for(int j = 0; j < count[j]; j++){
                    builder.append((char)('a' + i));
                }
            }
        }
        return builder.toString();
    }

}
